Although modeling systems used in Mechanical Computer Aided Design and in animation are expanding their geometric domain to include free form surfaces, polygonal models remain the primary 3D representation used in the manufacturing, architectural, Geographic Information Systems, geoscience, and entertainment industries. Polygonal models are particularly effective for hardware assisted rendering, which is important for video-games, virtual reality, fly-through, and electronic mock-up applications involving complex Computer Aided Design (CAD) models.
Since methods are known in the prior art for easily and efficiently triangulating arbitrary polygonal faces, it is sufficient to consider geometric models which are defined by triangular meshes. For example, a method to triangulate the faces of a polygonal model is described by Ronfard, R. and Rossignac, J. in "Triangulating multiply-connected polygons: A simple, yet efficient algorithm", Computer Graphics Forum, V. 13, No. 3, 1994, pp. 281-292.
A "triangular mesh" is defined by the position of its vertices ("geometry"), which are N-dimensional vectors, by the association between each triangle and its sustaining vertices ("connectivity"), and by colors, normals, and texture coordinates ("properties"), which do not affect the geometry, but influence the way it is shaded.
A triangular mesh with V vertices and T triangles is typically represented in the prior art (for example, as described by Foley et.al. in "Computer Graphics: Principles and Practice", Addison-Wesley, 1990) by a "vertex positions array", a "triangle array", and (optionally) one or more "property arrays". The position of each vertex of the triangular mesh is represented in the vertex positions array by N floating point coordinates. Each triangle of the triangular mesh is represented in the triangle array by three indices to the vertex positions array.
A triangular mesh may also have continuous or discrete properties, such as colors, normals, and texture coordinates, associated with its vertices or triangles. To model various discontinuous phenomena on the triangular mesh, properties can also be associated with each vertex of each triangle. These (triangle,vertex) pairs are called "corners", and the corresponding properties "corner" properties. These corner properties are represented in the optional property arrays.
Triangular meshes are typically classified (for example, as described by Hoffmann, C., "Geometric and Solid Modeling", Morgan Kaufmann, 1989) as manifolds and non-manifolds. An "edge" of a triangular mesh is a pair of vertices in a triangle, without taking into account the order of the two vertices within the edge. The two vertices of an edge are called endpoints of the edge. The triangle is said to be incident to the edge, and the edge incident to the vertices. Two triangles sharing an edge are said to be adjacent. Two edges sharing a vertex are said to be adjacent. The set of triangles that share a vertex are referred to as the star of the vertex. The number of triangles in the star of a vertex is referred to herein as the valence of the vertex. The link of a vertex is obtained by connecting all adjacent edges bounding the star of the vertex and discarding from the list of edges so formed the edges incident to the vertex. If the link has one component, and is not intersecting itself, the vertex is said to be a regular vertex, otherwise it is referred to as a singular vertex. For a regular vertex, if the link is closed, meaning that the first end point of the first edge of the link is the same as the last end point of the last edge, the vertex is an interior regular vertex, otherwise it is a boundary vertex.
The edges of a triangular mesh define a partition of the vertices of the triangular mesh into one or more disjoint subsets of vertices such that the two endpoints of each edge of the triangular mesh belong to the same subset. This partition of the vertices of the triangular mesh defines an associated partition of the triangles of the triangular mesh into one or more disjoint subsets of triangles, which are in one to one correspondence with the subsets of vertices. The subset of triangles associated with a subset of vertices is composed of all the triangles of the triangular mesh with vertices in the subset of vertices. If the triangular mesh has properties, the partition of the vertices also defines corresponding partitions of the properties in a similar manner. Each subset of vertices, the corresponding subset of triangles, and (optionally) the corresponding subsets of properties define a new triangular mesh which is called a "connected component" of the triangular mesh.
A triangular mesh is referred to as a "manifold triangular mesh" if the following two conditions are satisfied: 1) if any two triangles of the triangular mesh intersect, the intersection is either a common vertex or a common edge; and 2) all the vertices of the triangular mesh are regular vertices, which implies that each edge of the triangular mesh is shared by at most two triangles.
An edge of a manifold triangular mesh may have either one or two incident triangles. An "interior edge" is an edge with two incident triangles. A "boundary edge" is an edge with one incident triangle. It is known in the prior art that the endpoints of the boundary edges of a manifold triangular mesh are boundary vertices, and that the boundary vertices of a manifold triangular mesh are endpoints of the boundary edges. The boundary edges of a manifold triangular mesh can be partitioned into one or more disjoint subsets of boundary edges referred to as "boundaries", such that two boundary edges which share a boundary vertex as a common endpoint belong to the same boundary. It is also known in the prior art that each boundary vertex of a manifold triangular mesh is the endpoint of exactly two boundary edges.
Since methods are known in the prior art for converting non-manifold polygonal models into manifold polygonal models, it is sufficient to consider triangular meshes which are manifolds. A method to convert non-manifold polygonal models into manifold polygonal models is described in "Method to Convert Non-Manifold Polyhedral Surfaces into Manifold Surfaces", U.S. patent application Ser. No. 08/840,001, filed on Apr. 24, 1997, by A. Gueziec and G. Taubin, herein incorporated by reference in its entirety.
A manifold triangular mesh can be changed or edited to produce a new manifold triangular mesh, by modifying either its geometry, its connectivity, or both its geometry and its connectivity. Optionally, the change may also involve a modification of the properties of the manifold triangular mesh.
It is known in the prior art (described by Massey, W. S., in "Algebraic Topology: An Introduction", Hartcourt, Brace & World, Inc., New York, 1967) that the following types of changes on a manifold triangular mesh , referred to herein as "mesh surgery operations", produce a new manifold triangular mesh:
1) cut the manifold through a subset of its edges; 2) identify, or stitch, adjacent pairs of boundaries edges; 3) delete one or more connected components; 4) add one or more connected components; and 5) move vertices and (optionally) properties.
Of most interest to the teaching of this invention is to represent sequences of mesh surgery operations applied to an initial manifold triangular mesh in compressed form for efficient storage and transmission, and efficient decompression methods. For the purposes of this disclosure a manifold triangular mesh followed by a sequence of mesh surgery operations is referred to as "changing mesh".
One significant advantage of applying mesh surgery operations to manifolds is that the boundaries are closed 1-D manifolds. This property results in a simplified description and encoding of some operations, such as adding a surface and other stitching operations, which only affect the surface boundaries.
Applications of changing meshes include, but are not limited to, a progressive transmission of multi-resolution models, and visualization of scientific data represented by time-dependent triangular meshes.
A multi-resolution polygonal model is a sequence of polygonal models, where each element of the sequence, referred to as a "level of detail", or simply as a "level", has more vertices and faces than the previous level. The first element of the sequence is referred to as the "lowest resolution level", and the last element of the sequence is referred to as the "highest resolution level".
When transmitting a multi-resolution polygonal model over a communications link or network, it is desirable to send the information necessary to reconstruct the levels in increasing order of level of detail, i.e., from low to high resolution, such that the receiver may render a level as soon as it has all of the information associated with the level. In this manner the user can interact with a rendered level before the system has all of the information necessary to render the next level. This can be referred to as a progressive representation and transmission.
Independent of transmission through computer networks, and to speed-up the visualization of large surface data sets, one may wish to progressively display a surface such that while the computer system used for displaying the data sets is busy preparing high resolution images, lower resolution images are quickly available for display and interaction using simplified models. For this type of application lower resolution levels of detail should be displayed first, and changes from one level to the next should be provided to the computer system.
In both Scientific Visualization applications and computer animations the connectivity of triangular meshes often changes over time. A good example of one such application is a weather simulation that is used for observing the evolution of a cloud formation over time. Clouds may be represented as iso-surfaces computed in regularly sampled three dimensional volume data. This particular application is described in "Three Dimensional Visualization for Support of Operational Forecasting at the 1996 Centennial Olympic Games" by L. A. Treinish and L. P. Rothfusz, which appeared in the 13th Conference on IIPS for Meteorology, Oceanography and Hydrology, in February 1997, Long Beach, Calif.
Prior art methods for representing surface changes include the following techniques, described by Hoppe's "Progressive Meshes", Proceedings of ACM SIGGRAPH'93, pp.99-108, by Welch and Witkin's "Free-Form Shape Design Using Triangulated Surfaces", Proceedings of ACM SIGGRAPH'97, by Popovic et al. "Progressive Simplicial Complexes", Proceedings of ACM SIGGRAPH'97, pp. 217-224 and by Puppo "Simplification, LOD and Multi-resolution--Principles and Applications", Eurographics'97 Tutorial Notes.
The technique of Hoppe builds a progressive mesh representation that consists of a description of the transition from a simplified mesh to the original mesh. Hoppe sends a succession of "vertex splits" in order to undo the edge collapses that he performed earlier. For each of these edge splits, he must specify the indices in the original mesh of the simplified vertex resulting from the collapse, as well as the indices of the neighboring vertices where the new triangles will be inserted. In addition, the displacement of the new vertex with respect to the previous position of the vertex must be specified.
One problem with Hoppe's Progressive Meshes technique is that each vertex split information contains a vertex identification (ID), the position of two vertices after splitting, and the relative position of two vertices in the neighborhood of the first vertex. This results in a requirement to transmit a considerable amount of information. Another drawback is that each individual vertex split must be specified. Hoppe's Progressive Meshes technique only permits one to represent and encode changes in the level of detail, not in the surface topology.
Welch and Witkin describe a system for interactive editing of triangular meshes where mesh surgery operations are allowed. However, in their description Welch and Witkin are not concerned with the compressed representation of the resulting sequences of editing operations.
The Progressive Simplicial Complexes technique of Popovic and Hoppe is a generalization of the Progressive Meshes technique to lines, surfaces and volumes. A vertex split is replaced with a "generalized vertex split". With respect to the vertex split, additional information is necessary to encode whether the added vertex will add a point, a line segment, a triangle, or a tetrahedron to the complex. Popovic's method allows one to change the topology, but the result of his technique is not necessarily a surface, and if it is a surface, it is not necessarily a manifold surface.
The Multi-Triangulation technique of Puppo et al. is essentially a method for representing several levels of detail of a surface simultaneously, using a directed acyclic graph whose nodes represent increases and decreases of the number of triangles and whose arcs represent the dependencies between such increases or decreases. Puppo et al. do not discuss how the levels of detail can be transmitted efficiently. Furthermore, it is not possible to change the surface topology using Puppo et al.'s method.
One method to compress manifold triangular meshes is described by Michael Deering in "Geometric compression", Proceedings of ACM Siggraph'95, pp 13-20, August 1995; and in European Patent Applications "Method and apparatus for geometric compression of three-dimensional graphics", EP 0 757 332 A2, filed May 8, 1996, by Michael Deering. In this method a stack-buffer is used to store 16 of the previously used vertices instead of having random access to all the vertices of the model. The triangles of the mesh are partitioned into "generalized triangle meshes". Triangles which belong to the same generalized triangle mesh may share vertices, which are transmitted only once using the stack-buffer. But vertices common to triangles which belong to different generalized triangle meshes must be duplicated. In this method the connectivity of the triangular mesh is lost. The vertex positions and properties are quantized and entropy encoded.
Another method to compress manifold triangular meshes is described in "Compression of Simple Geometric Models Using Spanning Trees", U.S. patent application Ser. No. 08/688,572 filed Jul. 30, 1996, by J. Rossignac and G. Taubin, and in "Compression of Geometric Models Using Spanning Trees", U.S. patent application Ser. No. 08/685,422 filed Jul. 30, 1996, by J. Rossignac and G. Taubin, which are incorporated by reference herein in their entireties. In these methods the connectivity of the triangular mesh is preserved without loss of information. In this scheme the vertices of the triangular mesh are organized into a "vertex spanning tree", and the triangles into a "triangle spanning tree". The vertex spanning tree is a sub-graph of the "graph of the polygonal model". The graph of a polygonal model is the graph defined by the vertices and edges of the polygonal model. And the triangle spanning tree is a sub-graph of the dual graph of the triangular mesh. The "dual graph of the triangle mesh" is the graph defined by the faces and edges of the triangle mesh. The order of traversal of both trees define an order for the edges of triangular mesh. The vertex positions and properties are quantized and entropy encoded. The prior art concerning graphs and trees is described by R. E. Tarjan in "Data Structures and Network Algorithms", SIAM, 1983.
However, neither Deering's nor Rossignac and Taubin's methods address the compressed representation of changing meshes. Although Hoppe's and Popovic's methods address a limited class of changing meshes, they are not efficient compression schemes. They require in the order of N.log(N) total bits of data to represent a triangular mesh of N vertices in progressive form. On the other hand, Rossignac and Taubin method require in the order of N total bits of data to represent a single resolution mesh in compressed form.
In summary, of the prior art techniques known to the inventors the triangle mesh compression schemes do not adequately address the compression of changing meshes, while some are restricted to particular cases of changing meshes but are not efficient compression schemes, and while others do not solve the problem of representing changing meshes in compressed form. There is thus a long felt need to overcome these and other problems of the prior art and to provide an efficient method for encoding changing meshes.